package stack;

import java.util.Arrays;
import java.util.Stack;

public class MyStack {

    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_CAPACITY = 10;
    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
    }

    //压栈
    public void push(int val) {
        //扩容
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
    }
    //判满
    public boolean isFull() {
        if(usedSize == elem.length) {
            return true;
        }
        return false;
    }
    //删除栈顶元素
    public int pop() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空了！");
        }
        int oldVal = elem[usedSize - 1];
        usedSize--;
        return  oldVal;
    }
    //判空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    //获取栈顶元素 但不删除
    public int peek() {
        if(isEmpty()) {
            throw  new EmptyStackException("栈为空了！");
        }
        return elem[usedSize - 1];
    }
    public int getUsedSize() {
        return usedSize;
    }


    //括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //左括号就入栈
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.empty()) {
                    return false;
                }
                //获取栈顶元素
                char top = stack.peek();
                if((ch == ')' && top == '(') || (ch == ']' && top == '[') ||(ch == '}' && top == '{')) {
                    stack.pop();
                } else {
                    //左右括号不匹配
                    return false;
                }
            }
        }

        if(stack.empty()) {
            return true;
        }else {
            //左括号多
            return false;
        }
    }
    //逆波兰表达式
    public int valRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x : tokens) {

            //判断是否是加减乘除 不是就入栈
            if(!isOperation(x)) {
                stack.push(Integer.parseInt(x));//以整型入栈
            } else{
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (x) {
                    case "+" :
                        stack.push(num1 + num2);
                        break;
                    case "-" :
                        stack.push(num1 - num2);
                        break;
                    case "*" :
                        stack.push(num1 * num2);
                        break;
                    case "/" :
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    private boolean isOperation(String opera) {
        if(opera.equals("+") || opera.equals("-") || opera.equals("*") || opera.equals("/")) {
            return true;
        } else {
            return false;
        }
    }

    //出入栈次序匹配
    public boolean isPopOder(int[] pushA,int[] popA) {
        if(pushA.length == 0 || popA.length == 0) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while(j < popA.length && !stack.isEmpty() && stack.peek().equals(popA[j])) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

